package com.ftg.learn.chapter17.table;


import com.mysql.cj.x.protobuf.MysqlxCrud;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * 1、今天我们准备聊map
 *  -- 看一些说明
 *      基本类型[]  定长数组
 *      vector 动态数组
 *      -- 链表
 *      -- 用数组自己封装过链表
 *      -- List接口看成是线性表 有序可重复
 *          --- Arraylist底层数组
 *          --- Linkedlist 双向链表
 *      --set 接口线性   无序不可重复的
 *          -- hashset (hash结构 底层就是hashmap)
 *          -- treeset (树)
 *  -- 树形结构 ： 二叉树 （满二叉树|平衡二叉对 |AVl树（左旋  右旋）校招）
 *      -- red/back tree 红黑树
 *  -- 逻辑数据结构 （集合类） ： 自定义的java类（底层  要不就是数组  链）
 *      --二叉树的节点，每个节点下面最多有三个元素  数据项  左子树  右子树
 *
 * @author KangJx
 * @date 2021/8/9
 */
public class LearnTable<T extends Number> {

    /**
     * 任何一颗数都要有一个根节点
     * 有没有重复数据  有回2  没有回3
     * Set 不可以存重复数据 Treeset()
     */
    private Node<T> root;

    /**
     * 1、解决问题
     * 1.1 以后如果遇到了要用到快速查找，二叉查找树
     * 1.2 数据库 （可以存储大量元素的软件，用了快速查找 [索引：二叉查找树 B+ 红黑树]）
     *
     * 递归 : 给大家10分钟时间进行自我分析 以及代码编写
     *
     *  我们没有办法 完成所有节点的判断
     *    也就是说按原来写我们只能进行root节点的判断 ！
     *      小的放到left
     *      大的放到right
     *    我们希望所有的节点全要按照这个方式来完成
     *      我们代码进行完善，也就是说我们要把每一个节点全部进行原来的操作
     *          不能只对root进行大小判断 ，要对每一个节点全部进行相应的判断
     *`    当第一次执行add(3) --> add(root,3)
     *     当执行add(5) -> add(null , 5); -- root.right = add(null,5); -- root.right = new node(5,null,null)
     *      - root=3 root.left = null root.right = 5 root.right.left = null root.right.right = null
     *      当行扫add(1) - > node.left = add(root.left,1); - >node.left = add(null,1); ->node.left=new node(1,null,null)
     *      -root 3 root.left = 1 root.left.left = null root.left.right = null
     *              root.right = 5 root.right.left = null root.right.right = null
     *      当执行add(4); - add(root,4) - > node.right = add(node.right,4); node.right = add(5,4);
     *      root.right.left = add(5.left,4); root.right.left = add(null,4); - root.right.left = new node(4,null,null)
     *      -
     *                                               root 3
     *                      root.left = 1                              root.right = 5
     *      root.left.left = null      root.left.right = null    root.right.left = 4    root.right.right =null
     *                                             root.right.left.left = null   root.right.left.right = null
     *
     *  二叉树的遍历 问题:
     *
     *
     *
     *     node 等于root根
     * @param t1
     */
    private Node<T> add(Node<T> node,T t1){
        //第一次的时候，我们的node就是root 就是 一个新的节点值为3
        //第二次的时候，我们的nde不是root 而是(root.right)null --> node(5,null,null)
        if(null == node){
            return new Node<>(t1);
        }

        //想法是样的如果说 t1.val 小于 当前节点val 当前节点的左子树
        //1、能不能让两个类进行比较 大小？
        //面向对象的模板 堆里面的！所以类指向的是一个内存地址，所以两个类比较 大小没有意义
//        --- 两个类不能比较大小  错
        //也就是说我们一般对类进行比较大小的时候 往往都 是对类内部的唯一性元素比较 大小(number)

        double val = t1.doubleValue();
        double nodeVal = node.val.doubleValue();
        //转换完成以后  t1 double root.val  double compare > < =
        if(val < nodeVal){
            node.left = add(node.left,t1);
            //走的是else if
        }else if(val > nodeVal){
            //root.right = add(node.right,t1);
            //root.right = add(root.right,t1); --> root 3 null null root.right == null
            node.right = add(node.right,t1);
        }else{
            return node;
        }
        return node;
    }

    /**
     * 对开发人员开放的
     * @param val
     * add(3); -- >root - new node(3,null,null);
     * add(5);
     * add(1);
     * add(4);
     * add(4);
     * 我们的想法是在首节点判断 this.getroot();
     */
    public void add(T val){
        //我的添加的操作其它就是对root进行添加
        this.root = this.add(this.getRoot(),val);
        //如果root为空
//        root = new node(val,null,null);第一个节点
    }

    /**
     * 做先序遍历
     * pre - Order : 先序  ： 根在最左侧  根左右
     * 在方法里面定义 一个常量list final 修改的变量本身不能改变
     * @return
     */
    public void preOrder(final List<T> list,Node<T> t1){
        if(t1 == null){
            return;
        }
        list.add(t1.val);
        preOrder(list,t1.left);
        preOrder(list,t1.right);
    }

    /**
     *  pre-order   :   先序遍历  根左右
     *  in -order   :   中序遍历  左根右
     *  post-order  :   后序遍历  左右根
     *  -- 层遍历
     * @param list
     * @param t1
     */
    public void inOrder(final List<T> list,Node<T> t1){
        if(t1 == null){
            return;
        }
        preOrder(list,t1.left);
        list.add(t1.val);
        preOrder(list,t1.right);
    }

    /**
     * 判断当前节点curr 和 所有子节点里面是否有t1这个数据
     * @param curr  当前节点
     * @param t1    目标数据
     * @return    true|false
     */
    public boolean findNodeWithVal(Node<T> curr,T t1){
        if(curr == null){
            return false;
        }
        double d1 = t1.doubleValue();
        double d2 = curr.val.doubleValue();
        if(d1 == d2){
            return true;
        }
        return d1 > d2 ? findNodeWithVal(curr.right,t1) : findNodeWithVal(curr.left , t1);
    }

    /**
     * 从根节点上面判断是否存在t1
     * @param t1
     * @return
     */
    public boolean findNodeWithVal(T t1){
        return this.findNodeWithVal(this.getRoot(),t1);
    }


    /**
     * 后序遍历
     * postorder : 后序遍历  : 总根一定在最后面  先左再右再根
     * @param list
     * @param t1
     */
    public void postOrder(final List<T> list,Node<T> t1){
        if(t1 == null){
            return;
        }
        preOrder(list,t1.left);
        preOrder(list,t1.right);
        list.add(t1.val);
    }

    /**
     * 获取当前树的根点的方法
     * @return
     */
    public Node<T> getRoot() {
        return root;
    }


    /**
     * 树的节点类:二叉树  实现搜索二叉树 . 顶级大于左子树 小于右子树
     * @param <T> 要存储的类型
     */
   public class Node<T extends Number>{
       /**
        * 数据项s
        */
       T val;

       /**
        * 左子树
        */
       Node<T> left;

       /**
        * 右子树
        */
       Node<T> right;

       public Node(T val,Node<T> left,Node<T> right){
           this.val = val;
           this.left = left;
           this.right = right;
       }


        public Node(T val){
            this.val = val;
            this.left = null;
            this.right = null;
        }
    }

    /**
     * 获得内部类的节点
     * @param val
     * @param left
     * @param right
     * @return
     */
    public Node<T> getNode(T val,Node<T> left,Node<T> right){
       return new Node(val,left,right);
    }

    public static void main(String[] args) {
        LearnTable<Integer>  lt = new LearnTable<>();
        lt.add(23);
        lt.add(45);
        lt.add(3);
        lt.add(37);
        List<Integer> list=new ArrayList<>();
        lt.inOrder(list,lt.getRoot());
        System.out.println(list);

        System.out.println(lt.findNodeWithVal(41));
    }







}
